• In this Section we introduce the general framework of nonlinear classification, along with many examples.

• These examples are all low dimensional, allowing us to visually examine patterns in the data and propose appropriate nonlinearities, which we can (as we will see) very quickly inject into our linear supervised paradigm to produce nonlinear classifications.

• Just as with the previous Section by walking through these examples we flush out a number important concepts in concrete terms, coding principles, and jargon-terms in a relatively simple environment that will be omnipresent in our discussion of nonlinear learning going forward.

Activate next cell to toggle code on and off

from IPython.display import display
from IPython.display import HTML
import IPython.core.display as di # Example: di.display_html('<h3>%s:</h3>' % str, raw=True)

# This line will hide code by default when the notebook is eåxported as HTML
di.display_html('<script>jQuery(function() {if (jQuery("body.notebook_app").length == 0) { jQuery(".input_area").toggle(); jQuery(".prompt").toggle();}});</script>', raw=True)

# This line will add a button to toggle visibility of code blocks, for use with the HTML export version
di.display_html('''<button onclick="jQuery('.input_area').toggle(); jQuery('.prompt').toggle();">Toggle code</button>''', raw=True)

Toggle code

12.2.1 Modeling principles linear and nonlinear two class classification

• with two class linear classification we aim at determinig the proper parameters $\mathbf{w}$ of a linear model

\begin{equation} \text{model}\left(\mathbf{x},\mathbf{w}\right) = \mathbf{x}^T \mathbf{w} \end{equation}

that the corresponding linear decision boundary

\begin{equation} \text{model}\left(\mathbf{x},\mathbf{w}\right) = \mathbf{x}^T \mathbf{w} = 0 \end{equation}

separates the two classes as well as is possible using a linear model

• in Chapter 9 we saw several cost functions of this model, like softmax

\begin{equation} g\left(\mathbf{w}\right) = \frac{1}{P}\sum_{p=1}^{P}\text{log}\left(1 + e^{-y_p\text{model}\left(\mathbf{x}_p,\mathbf{w}\right)}\right) \end{equation}

whose minimum provides us with the weights that service our ideal as best as possible

Example 1. The perfect dataset for linear two class classification

• for linear two-classification our perfect dataset would consist of points where $\text{model}\left(\mathbf{x}_p,\mathbf{w}\right) = y_p$, i.e., points lying perfectly on the step function with linear boundary given by $\text{model}\left(\mathbf{x},\mathbf{w}\right) = 0$.

• if we examine any of the arguments in Chaper 9 used to derive logistic regression, the perceptron, or support vector machines nothing in any of these arguments relied on our use of a linear model

• a nonlinear assumption about how the classes of a dataset are distributed would lead to the same formulae

• e.g.,

\begin{equation} \text{model}\left(\mathbf{x},\mathbf{w}\right) = w_0^{\,} + {w}_{1}^{\,}\,f\left(\mathbf{x}_p\right) \end{equation}

where here $f$ is some parameterized or unparameterized nonlinear function or feature transformation

• just replace original linear model with one like this in softmax, minimize via gradient descent, etc.,

• just as with nonlinear regression we could in general just as well use a weighted sum of $B$ nonlinear functions

\begin{equation} \text{model}\left(\mathbf{x},\mathbf{w}\right) = w_0 + {w}_{1}\,f_1\left(\mathbf{x}_p\right) + {w}_{2}\,f_2\left(\mathbf{x}_p\right) + \cdots + w_B\,f_B\left(\mathbf{x}_p\right) \end{equation}

where $f_1,\,f_2,\,...\,f_B$ are nonlinear parameterized or unparameterized feature transformations and $w_0$ through $w_B$

Example 2. The perfect dataset for two class nonlinear classification

• for nonlinear two-classification our perfect dataset would consist of points where the nonlinear decision boundary given by $\text{model}\left(\mathbf{x}_p,\mathbf{w}\right) = 0$ perfectly separates the data

12.2.2. Simple examples of nonlinear two class classification

• here we walk through a number of simple examples of nonlinear classification where we can determine - by eye - a proper nonlinear model

• doing this helps flush out a number of mathematical and programming concepts that are crucial going forward

• first up: its time to officially abstract our cost function(s) for two-class classification e.g., softmax

def softmax(w):
    cost = np.sum(np.log(1 + np.exp(-y*model(x,w))))
    return cost/float(len(y))

• this works regardless of the model - linear or nonlinear - so we can push it to the back

• we can also abstract our model function too, since will look essentially the same throughout all examples

• with the inclusion of general feature transformation(s) our model will always look like

# an implementation of our model employing a nonlinear feature transformation
def model(x,w):    
    # feature transformation 
    f = feature_transforms(x,w[0])
    
    # tack a 1 onto the top of each input point all at once
    o = np.ones((1,np.shape(f)[1]))
    f = np.vstack((o,f))
    
    # compute linear combination and return
    a = np.dot(f.T,w[1])
    return a

Example 4. Linear classification

• employ the simple linear feature transformation

\begin{equation} f\left(x\right) = x \end{equation}

• our model is then (reduces to our typical linear model)

\begin{equation} \text{model}\left(x,\mathbf{w}_{\!}\right) = w_0 + w_{1\,}f\left(x\right). \end{equation}

# the trivial linear feature transformation
def feature_transforms(x):      
    return x

# parameters for our two runs of gradient descent
w = 0.1*np.random.randn(2,1); max_its = 500; alpha_choice = 10**(2)

# run on normalized data
run = nonlib.basic_runner.Setup(x,y,feature_transforms,'softmax',normalize = 'standard')
run.fit(w=w,alpha_choice = alpha_choice,max_its = max_its)

• tune via gradient descent

Example 4. A one dimensional example of nonlinear classification

• what sort of simple function crosses the horizontal axis twice?

</figure> </p>

• here we have two unparameterized feature transformations: the identity $f_1(x) = x$ and the quadratic term $f_2(x) = x^2$

• our model is then

\begin{equation} \text{model}(x,\mathbf{w}) = w_0 + w_1\,f_1(x) + w_2\,f_2(x) \end{equation}

• Python implementation

# our quadratic feature transformation
def feature_transforms(x):
    # calculate feature transform
    f = np.array([(x.flatten()**d) for d in range(1,3)])   
    return f

# parameters for our two runs of gradient descent
w = 0.1*np.random.randn(3,1); max_its = 500; alpha_choice = 10**(2)

# run on normalized data
run = nonlib.basic_runner.Setup(x,y,feature_transforms,'softmax',normalize = 'standard')
run.fit(w=w,alpha_choice = alpha_choice,max_its = max_its)

• tune via gradient descent

• akin to regression, what is a nonlinear model in the original space is linear in the feature transformed space

Example 5. Finding an elliptical boundary separating two classes

• looks like some sort of elliptical decision boundary centered at the origin might do a fine job of classification

• so a model of the form

\begin{equation} \text{model}(\mathbf{x},\mathbf{w}) = w_0^{\,} + w_1^{\,} x_1^2 + w_2^{\,}x_2^2. \end{equation}

• here we have used two feature transformations $f_1(\mathbf{x})=x_1^2$ and $f_2(\mathbf{x}) = x_2^2$

• in Python our feature_transforms function

# a elliptical feature transformation
def feature_transforms(x):
    # calculate feature transform
    f = x**2  
    return f

• now we minimize the softmax above via gradient descent.

# parameters for our two runs of gradient descent
w = 0.1*np.random.randn(3,1); max_its = 200; alpha_choice = 10**(1)

# run on normalized data
run = nonlib.basic_runner.Setup(x,y,feature_transforms,'softmax',normalize = 'none')
run.fit(w=w,alpha_choice = alpha_choice,max_its = max_its)

Example 6. Using a parameterized sinusoid to classify stripes of data

• a completely parameterized sinusoid of two inputs

\begin{equation} f\left(\mathbf{x}\right) = \text{sin}\left(w_0 + w_1x_1 + w_2x_2\right). \end{equation}

• our model a linear combination of this nonlinear feature transformation as

\begin{equation} \text{model}\left(\mathbf{x},\mathbf{w}_{\!}\right) = w_3 + w_{4\,}f\left(\mathbf{x},\mathbf{w}\right). \end{equation}

- in `Python` our `feature_transforms` function

# our nonlinearity, known as a feature transformation
def feature_transforms(x,w):
    # tack a 1 onto the top of each input point all at once
    o = np.ones((1,np.shape(x)[1]))
    x = np.vstack((o,x))
        
    # calculate feature transform
    f = np.sin(np.dot((x).T,w)).T
    return f

• tune via gradient descent using softmax cost

# parameters for our two runs of gradient descent
scale = 2
w = [scale*np.random.randn(3,1),scale*np.random.randn(2,1)]
max_its = 1000; alpha_choice = 10**(-1)

# run on normalized data
run = nonlib.basic_runner.Setup(x,y,feature_transforms,'softmax',normalize = 'standard')
run.fit(w=w,alpha_choice = alpha_choice,max_its = max_its)

12.2.3 Modeling principles linear and nonlinear multiclass classification

• can inject nonlinearity into our mulitclass classification in the same way we have done for two-class scenario

• regardless of framework we always aim to learn $C$ classifiers, do the same thing we have done above for each

• simply inject nonlinear feature transforms in the same way we have seen done above

• some small technical differences, see notes for details

12.2.4 Simple examples of nonlinear multiclass classification

Example 7. Nonlinear One-versus-All multiclass classification

• looks like the classes of this dataset can be cleanly separated via elliptical boundaries, but the distribution of each class is not centered at the origin

• to capture this behavior we will use a full degree 2 polynomial expansion of the input

• terms from a general degree $D$ polynomial always take the form

\begin{equation} f\left(\mathbf{x}\right) = x_1^ix_2^j \end{equation}

where $i + j \leq D$.

• to employ all of them for $D = 2$ means using the following nonlinear model

\begin{equation} \text{model}\left(\mathbf{x},\mathbf{w}\right) = w_0 + w_1x_1 + w_2x_2 + w_3x_1x_2 + w_4x_1^2 + w_5x_2^2 \end{equation}

In Python we can implement this in a feature_transforms as follows.

# a elliptical feature transformation
def feature_transforms(x):
    # calculate feature transform
    f = []
    for i in range(0,D):
        for j in range(0,D-i):
            if i > 0 or j > 0:
                term = (x[0,:]**i)*((x[1,:])**j)
                f.append(term)
    return np.array(f)

# run one versus all
max_its = 1500; alpha_choice = 10**(0); w = 0.1*np.random.randn(6,1)
combined_weights, count_history = nonlib.one_versus_all.train(x,y,feature_transforms,alpha_choice = alpha_choice,max_its = max_its,w = w)

• Use One-versus-All framework, softmax cost and gradient descent for each classifier

Example 8. Nonlinear multiclass softmax classification

• repeat previous experiment, but with multiclass softmax cost function

# parameters for our two runs of gradient descent
w = 0.1*np.random.randn(6,3); max_its = 1500; alpha_choice = 10**(0)

# run on normalized data
run = nonlib.basic_runner.Setup(x,y,feature_transforms,'multiclass_softmax',normalize = 'standard')
run.fit(w=w,alpha_choice = alpha_choice,max_its = max_its)